Binary Search Checklist

https://gyazo.com/3adb1ed9f7f843ada150d675bffb61a3

Check the four components of [dichotomous search

1: Is f(x) correct?

I can't help it if I'm wrong here.

You should write down some patterns and check them out.

2: Does a large/small comparison involve an equal sign?

Depends on whether you choose left or right when there is no matching value.

https://gyazo.com/f387019b4af042257419dac27b4a501d

If it matches, that's it, if not, if we choose left, we need to search for f(x)=T and f(x)<T to be left, and then return left.

Some types of problems can't be separated from 1 and 2.

In that case, 1 becomes an implementation that returns bool.

3: Is the initial value of left appropriate?

Check whether the initial value satisfies the inequality to be satisfied by LEFT based on 2.

4: Is the initial value of right appropriate?

code:python

def solve(N, K, AS):

left = 0 # (3)

right = max(AS) # (4)

while left < right - 1:

x = (left + right) // 2

y = f(x) # (1)

if y > K: # (2)

left = x

else:

right = x

return right

---